package hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class copyRandomList {
    public Node copyRandomList(Node head) {
        // 1个AarrayList来记录每个节点对应的 random，一个HashMap来记录 每个节点的下标和地址
        /**
         * 三次遍历
         * 1. 复制链表，random暂且不处理；Map1记录 每次的节点和head下标;Map2记录 新节点和下标
         * 2. 使用List.que记录 每个head节点对应的head下标
         * 3. 设置 新链表的random节点
         */
        List<Integer> que = new ArrayList<>();
        Map<Node,Integer> map1 = new HashMap<>();
        Map<Integer,Node> map2 = new HashMap<>();
        Node ret = new Node(0);
        Node cur = ret;
        Node curHead = head;
        ret.next = head;
        int index = 0;
        //第一次遍历
        while(curHead != null) {
            //拷贝节点
            Node temp = new Node(curHead.val);
            //Map1记录
            map1.put(curHead,index);
            //Map2 记录
            map2.put(index++,temp);
            cur.next = temp;
            cur = cur.next;
            curHead = curHead.next;
        }
        //第二次遍历
        curHead = head;
        while(curHead != null) {
            if(curHead.random == null) {
                que.add(-1);
            }else {
                que.add(map1.get(curHead.random));
            }
            curHead = curHead.next;
        }
        // 第三次遍历 设置新链表的random
        cur = ret.next;
        for(int x : que) {
            if(x == -1) {
                cur.random = null;
            }else {
                cur.random = map2.get(x);
            }
            cur= cur.next;

        }
        return ret.next;

    }
}
